package demo4;

import java.util.*;

public class Solution {

    public int minSubArrayLen(int target, int[] nums) {
        int ret = Integer.MAX_VALUE, t = 0;

        for(int left = 0, right = 0; right < nums.length; right++){
            t += nums[right];

            while(t >= target){
                ret = Math.min(ret, right - left + 1);

                t -= nums[left++];
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    public String shortestBeautifulSubstring(String s, int k) {
        if(s.replace("0", "").length() < k){
            return "";
        }

        for(int size = k;  ; size++){
            String ret = "";
            for(int i = size; i <= s.length(); i++){
                String t = s.substring(i - size, i);
                if((ret.isEmpty() || t.compareTo(ret) < 0) && t.replace("0", "").length() == k){
                    ret = t;
                }
            }
            if(!ret.isEmpty()){
                return ret;
            }
        }
    }

    public String shortestBeautifulSubstring2(String s, int k) {
        if(s.replace("0", "").length() < k){
            return "";
        }

        char[] ch = s.toCharArray();
        String ret = s;
        for(int left = 0, right = 0, cnt = 0; right < ch.length; right++){
            cnt += ch[right] - '0';

            while(cnt > k || ch[left] == '0'){
                cnt -= ch[left++] - '0';
            }

            if(cnt == k){
                String t = s.substring(left, right + 1);
                if(t.length() < ret.length() || t.length() == ret.length() && t.compareTo(ret) < 0){
                    ret = t;
                }
            }
        }
        return ret;
    }
}
